:-dynamic llega/3.
:-dynamic autonomia/2.
%% Rutas aéreas predefinidas.

% llega(?origen, ?destino, ?tiempo)
llega(buenos_aires, mdq, 1).
llega(buenos_aires, cordoba, 2).
llega(buenos_aires, rio, 4).
llega(buenos_aires, madrid, 12).
llega(buenos_aires, atlanta, 11).
llega(mdq, buenos_aires, 1).
llega(cordoba, salta, 1).
llega(salta, buenos_aires, 2).
llega(rio, buenos_aires, 4).
llega(rio, new_york, 10).
llega(atlanta, new_york, 3).
llega(new_york, madrid, 9).
llega(madrid, lisboa, 1).
llega(madrid, buenos_aires, 12).
llega(lisboa, madrid, 1).
llega(new_york, buenos_aires, 11).

%% Aviones y sus autonomías.
% autonomia(?avion, ?horas)
autonomia(boeing_767, 15).
autonomia(airbus_a320, 9).
autonomia(boeing_747, 10).


%===========================================================
%% Predicados pedidos:
% ciudades(-Ciudades)

ciudades(Ciudades):- setof(C, esCiudadOrigen(C), Ciudades).
%===========================================================
% viajeDesde(+Origen,?Destino,-Recorrido,-Tiempo) -- Devuelve infinitos resultados.

% ciudades(C) instacia en C todas las cidades, tal como se pide en el ej1
% member(O,C) chequea que O sea una ciudad perteneciente al conjunto de ciudades
% head(R,O) chequea que el primer elemento de la lista solución R, sea la ciudad origen
% ultimoElemento(R,D) chequea que el destino sea el último elemento de la lista solucion R
% esCamino(R) chequea que los elementos de la lista R esten conectados, usando llega(O,D,T)
% duracionRecorrido(R,T) instancia en T el valor correspontiente a la suma del tiempo del recorrido R

viajeDesde(O,D,R,T) :- 
	ciudades(C), 
	member(O,C), 
	head(R,O), 
	ultimoElemento(R,D), 
	esCamino(R), 
	duracionRecorrido(R,T).

%===========================================================
% viajeSinCiclos(+Origen,?Destino,-Recorrido,-Tiempo)

% Se obtienen las ciudades de las que pueden partir vuelos.
% Usando esa lista de ciudades para no repetir en el recorrido, se obtienen
% los caminos posibles sin ciclo entre Origen y Destino.
% Por último se obtiene la duración del recorrido instanciado.
 
viajeSinCiclos(Origen,Destino, Recorrido,Tiempo) :- 
	ciudades(C),
	caminoSinCiclos(Origen, Destino, Recorrido, C),
	duracionRecorrido( Recorrido, Tiempo).
	
%===========================================================
% viajeMasCorto(+Origen,+Destino,-Recorrido,-Tiempo)

% Se obtienen todos los caminos sin ciclos entre Origen y Destino,
% luego se obtiene el recorrido más corto de esos recorridos y
% se obtiene la duración del mismo.

viajeMasCorto(Origen, Destino, Recorrido, Tiempo) :-
	todosLosCaminosSinCiclos( Origen, Destino, ListaRecorridos),
	caminoMasCorto( ListaRecorridos, Recorrido ),
	duracionRecorrido( Recorrido, Tiempo).
	
%===========================================================
% grafoCorrecto

% Determina que el grafo que se genera con los planes de vuelo mediante los
% hechos llega(_,_,_) sea un grafo conexo. Para ello se obtienen todas las
% ciudades y se debe cumplir que de todas las ciudades se puede llegar al resto.

grafoCorrecto :- 
	setof(X, esCiudad(X), L),
	todosConexosConList( L, L ).
	
%===========================================================	
% cubreDistancia(+Recorrido, ?Avion)

% Determina si el avion pasado puede realizar el recorrido. Para ello,
% el avion debe de tener la autonomía suficiente para volar cada una
% de las secciones del recorrido.
% Si el avion no es pasado, se instancia en Avion aquellos aviones que
% pueden realizar el recorrido pasado.

cubreDistancia([], _).
cubreDistancia([X], _).
cubreDistancia([X, Y | L], A) :- 
	llega( X, Y, Tv ),
	autonomia(A, Ta),
	Tv =< Ta,
	cubreDistancia([Y | L], A).

%===========================================================	
% vueloSinTransbordo(+Aerolinea, +Ciudad1, +Ciudad2, ?Tiempo, ?Avion)
% Se asume que en el estado de las aerolineas no se repiten ciudades.

% Se determina el avión y el tiempo minimo en que este puede realizar el viaje
% desde Ciudad1 hasta Ciudad2.
% Para cada avión que está en la Ciudad1, se obtiene el tiempo minimo que le lleva
% a ese avión realizar el viaje desde Ciudad1 hasta Ciudad2. Como pueden haber varios
% caminos con igual tiempo, se eliminan los repetidos.
vueloSinTransbordo([(Origen,Aviones) | RestoAerolinea], Origen, Destino, Tiempo, Avion) :-
	member(Avion,Aviones),
	setof(T,realizaViajeEnTiempoMinimo(Origen,Destino,Avion,T),TiemposDeLosViajes),
	member(Tiempo, TiemposDeLosViajes).	
vueloSinTransbordo([ _ | RestoAerolinea], Origen, Destino, Tiempo, Avion) :-
	vueloSinTransbordo( RestoAerolinea, Origen, Destino, Tiempo, Avion).

%% Descomentar si se usa un archivo separado para las pruebas.
?- [pruebas].

%Auxiliares (Ordenados alfabéticamente)

% A partir de una lista de recorridos se instancia el camino más corto de la lista
% caminoMasCorto( +ListaRecorridos, -MasCorto )
caminoMasCorto( [ X ], X ).
caminoMasCorto( [ X, Y | R ], Z ) :- 
	duracionRecorrido( X, TX ), 
	duracionRecorrido( Y, TY ),
	TY =< TX, 
	caminoMasCorto( [ Y | R ], Z ).
caminoMasCorto( [ X, Y | R ], Z ) :- 
	duracionRecorrido( X, TX ), 
	duracionRecorrido( Y, TY ),
	TX =< TY, 
	caminoMasCorto( [ X | R ], Z ).


% %Si no se pasa el Destino instanciado y el Recorrido, se instancian
% todos los caminos (Recorrido) desde el Origen al Destino sin ciclo, es
% decir, sin pasar dos veces por la misma ciudad.
% Se usa el parámetro Stack para saber por cuál ciudad ya se pasó.

% caminoSinCiclos( +O, ?D, -Rec, +Stack )
caminoSinCiclos( O, O, [O], _ ). 
caminoSinCiclos( O, D, Rec, Stack ) :-
	delete(Stack, O, NewStack),
	member(X, NewStack),
	llega( O, X, _),
	caminoSinCiclos( X, D, RestoRecorrido, NewStack ),
	append( [ O ], RestoRecorrido, Rec).

	
% duracionRecorrido( +Recorrido, -Tiempo)
duracionRecorrido( [], 0).
duracionRecorrido( [ X ], 0).
duracionRecorrido( [ X , Y | R ], Tiempo) :- 
	llega( X, Y, T1 ),
	duracionRecorrido( [ Y | R ], T2),
	Tiempo is T1 + T2.
	
esCamino([L]).
esCamino([L|LS]):- head(LS,D), llega(L,D,_), esCamino(LS).

% esCiudad(?X)
esCiudad(X) :- esCiudadOrigen(X).
esCiudad(X) :- esCiudadDestino(X), not(esCiudadOrigen(X)).

% esCiudadDestino(?X)
esCiudadDestino(X) :- llega(_,X,_).
	
% esCiudadOrigen(?C)
esCiudadOrigen(C) :- llega(C,_,_).

head([H|T],H).

%realizaViajeEnTiempoMinimo(+Origen, +Destino, +Avion, ?Tiempo)
realizaViajeEnTiempoMinimo(Origen, Destino, Avion, Tiempo) :-
	setof(R, vueloDirectoOConEscala(Origen, Destino, Avion, R), Recorridos),
	caminoMasCorto(Recorridos, Recorrido),
	duracionRecorrido(Recorrido,Tiempo).

tail([H|T],T).

% todosConexosCon( +Ciudad, +CiudadesACheckear, +TodasLasCiudades )
todosConexosCon( Ciudad, [], _ ).
todosConexosCon( Ciudad, [ X | L ], TodasLasCiudades ) :- 
	caminoSinCiclos( Ciudad, X, _, TodasLasCiudades ),
	caminoSinCiclos( X, Ciudad, _, TodasLasCiudades ),
	todosConexosCon( Ciudad, L, TodasLasCiudades ).
	
% todosConexosConList( +CiudadesACheckear, +TodasLasCiudades )
todosConexosConList( [], _ ).
todosConexosConList( [ X | L ], TodasLasCiudades ) :- 
	todosConexosCon( X, TodasLasCiudades, TodasLasCiudades),
	todosConexosConList( L, TodasLasCiudades ).
	
% todosLosCaminosSinCiclos( +O, +D, -ListaRecorridos)
todosLosCaminosSinCiclos( O, D, ListaRecorridos) :-
	ciudades(C),
	setof(Recorrido, caminoSinCiclos( O, D, Recorrido, C ), ListaRecorridos).
	
ultimoElemento(L,E) :- reverse(L,R), head(R,E).

%vueloDirectoOConEscala(+Origen, +Destino, +Avion, ?Recorrido)
vueloDirectoOConEscala(Origen, Destino, Avion, Recorrido) :-
	viajeSinCiclos(Origen, Destino, Recorrido, _ ),
	cubreDistancia(Recorrido, Avion).
